package pers.qianyu.month_202101.date_20210129;

import java.util.*;

/**
 * 64. 字符流中第一个只出现一次的字符
 * https://www.acwing.com/problem/content/60/
 *
 * @author mizzle rain
 * @date 2021年1月29日15:01:05
 */
public class FirstAppearingOnce {
    private int[] map = new int[128];
    private Queue<Character> q = new LinkedList<>();

    //Insert one char from stringstream
    public void insert(char ch) {
        if (++map[ch] > 1) {
            while (!q.isEmpty() && map[q.peek()] > 1) q.poll();
        } else {
            q.offer(ch);
        }
    }

    //return the first appearence once char in current stringstream
    public char firstAppearingOnce() {
        return q.isEmpty() ? '#' : q.peek();
    }

    public static void main(String[] args) {
        FirstAppearingOnce s = new FirstAppearingOnce();
        s.insert('g');
        System.out.println(s.firstAppearingOnce());
        s.insert('o');
        System.out.println(s.firstAppearingOnce());
        s.insert('a');
        System.out.println(s.firstAppearingOnce());
        s.insert('g');
        System.out.println(s.firstAppearingOnce());
        s.insert('e');
        System.out.println(s.firstAppearingOnce());
    }
}
